package com.lw.leetcode.arr.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 757. 设置交集大小至少为2
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/22 9:07
 */
public class IntersectionSizeTwo {

    public static void main(String[] args) {
        IntersectionSizeTwo test = new IntersectionSizeTwo();

        // 3
        int[][] intervals = {{1, 3}, {1, 4}, {2, 5}, {3, 5}};

        // 5
//        int[][] intervals = {{1, 2}, {2, 3}, {2, 4}, {4, 5}};

        // 2
//        int[][] intervals = {{1, 2}, {1, 2}};

        // 4
//        int[][] intervals = {{1, 2}, {6, 7}};

        // 5
//        int[][] intervals = {{2, 10}, {3, 7}, {3, 15}, {4, 11}, {6, 12}, {6, 16}, {7, 8}, {7, 11}, {7, 15}, {11, 12}};


        // 7
//        int[][] intervals = {{1, 3}, {4, 9}, {0, 10}, {6, 7}, {1, 2}, {0, 6}, {7, 9}, {0, 1}, {2, 5}, {6, 8}};

        int i = test.intersectionSizeTwo(intervals);
        System.out.println(i);
    }

    public int intersectionSizeTwo(int[][] intervals) {
        int length = intervals.length;
        if (length == 1) {
            return 2;
        }
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        int b = intervals[0][1];
        int a = b - 1;
        int count = 2;
        for (int i = 1; i < length; i++) {
            int[] arr = intervals[i];
            int st = arr[0];
            int end = arr[1];
            if (b < st) {
                count += 2;
                a = end - 1;
                b = end;
            } else if (a < st) {
                count++;
                a = Math.min(end - 1, b);
                b = end;
            } else {
                b = Math.min(end, b);
                a = Math.min(end - 1, a);
            }
        }
        return count;
    }

}
